package hashtable.isangram;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
 * 题目:给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

 * 思路：滑动窗口（固定窗口大小）+ 数组哈希表（因为都是小写字母，可以用长度为26的数组）

 * 步骤：
 *  1. 先统计字符串p中每个字符出现的次数，用数组pCount表示（长度为26）。
 *  2. 在字符串s上维护一个长度与p相同的滑动窗口，统计窗口内字符出现的次数，用数组sWindow表示。
 *  3. 比较两个数组是否相等，如果相等，则说明当前窗口内的子串是p的异位词，记录窗口的起始索引。
 *  4. 窗口向右滑动：每次滑动一位，去掉窗口最左边的字符，加入窗口右边的新字符（如果有），并更新sWindow数组。
 *  5. 重复步骤3和4，直到窗口滑动到s的末尾。
 */


public class FindAnagrams {
    public List<Integer> findAnagrams(String s, String p) {
        //用来存放最终结果
        List<Integer> res=new ArrayList<>();

        //统计s和p的长度
        int sLen=s.length();
        int pLen=p.length();

        //要求s的长度必须长于p，所以当s的长度小于p就没有异位词
        if(sLen<pLen){
            return res;
        }

        //初始化频率数组
        int[] pFre=new int[26];//记录 p 中每个字符的出现次数
        int[] window=new int[26];//当前窗口内字符的出现次数

        //统计p出现的字符频率
        for(char c : p.toCharArray()){
            pFre[c-'a']++;
        }

        //初始化检查窗口
        for(int i=0;i<pLen;i++){
            window[s.charAt(i)-'a']++;
        }

        //检查初始窗口
        if(Arrays.equals(pFre,window)){
            res.add(0);
        }

        //滑动窗口（从 pLen 开始向右移动,右边加入，左边移除)
        for(int right=pLen;right<sLen;right++){
            //加入新的字符(窗口右侧)
            char newChar=s.charAt(right);
            window[newChar-'a']++;

            //移除旧的字符
            char oldChar=s.charAt(right-pLen);
            window[oldChar-'a']--;

            //检查当前窗口是否为异位词
            if(Arrays.equals(pFre,window)){
                res.add(right-pLen+1);
            }
        }
        return res;

    }
}
